## 题意
给出$n$个点的完全图, 其中$m$条边被染色了, 只用0/1两种颜色. 对于剩下的边随便染色, 问总共有多少本质不同的三角形满足下面条件之一:
 
 * 三条边颜色都是1
 * 一条边颜色是0, 另外两条是1

## 题解
考虑补集的方法. 假设没有一条边被染色的话, 答案是$4 \times \binom{n}{3}$. 然后由于染色, 我们有些东西重复算了, 考虑减去, 大概分成3中情况.

###  1. 三条边都被染色
也就是一个三元环, 然后有4中三元环$(0,0,0)$, $(0, 0, 1)$, $(0, 1, 1)$和$(1, 1, 1)$, 多算的答案分别为4, 4, 3和3. 枚举所有三元环, 减去相应的部分即可

### 2. 两条边被染色
分成3中情况, $(0, 0)$, $(0,1)$和$(1, 1)$, 枚举一下, 发现多算的答案分别是4, 3和2. 枚举所有的这些边, 减去相应部分.

枚举可以这么考虑, 令$f_{i,a,b}$表示包含点$i$, 和$i$相邻的两条边颜色分别为$a$和$b$ $a \le b$的三元环的数目. $cnt_{i,a}$表示以$i$为端点的颜色为$a$的边的数目, 那么和$i$相邻的两条边颜色分别为$a$和$b$的非三元环数目就很容易算出来了.
$(0,0)$: $\binom{cnt_{i,0}}{2} - f_{i,0,0}$ 
$(0,1)$: $cnt_{i,0} \cdot cnt_{i,1} - f_{i,0,1}$
$(1,1)$: $\binom{cnt_{i,1}}{2} - f_{i,1,1}$ 

### 3. 只有一条边被染色
分为两种, 这条边颜色是0或者1, 同样枚举一下, 发现多算的答案是3和1. 枚举所有的这些边, 减去相应部分.

令$e_i$表示包含边$i$的三元环的数目, $deg_i$表示点$i$的度数.
枚举每条边$(a_i, b_i)$, 那么这条边的贡献是
0: $3(n - (deg_{a_i} + deg_{b_i} - e_i))$
1: $n - (deg_{a_i} + deg_{b_i} - e_i)$

显然问题剩下来就是如何快速枚举所有三元环, 因为知道三元环之后, 上面三种情况就很简单了.
$m \sqrt m \log n$的算法之前讲题的时候应该介绍过了, 虽然可以通过hash优化到$m \sqrt m$, 但是不够优美, 这里我介绍一个不依赖hash完全是$m \sqrt m$的算法.

首先把所有点按照$deg$的大小排序, 并重新标号. 然后给每一条无向边定向, 从标号小的连向编号大的. 那么我们可以发现, 每个三元环的出度数是这样的2, 1, 0, 分别令这三个点为$a, b,c$.  然后, 我们枚举$a,b$, 同事求出$a$的出边表和$b$的出边表的交集, 显然$c$必定属于这个交集. 

如果边表都是有序的, 那么合并的复杂度是边表的大小. 然后我们可以发现边表大小最大是$\sqrt {2m}$. 于是总的复杂度是$m \sqrt {2m}$.

证明如下:
把点按照度分类, 对于$deg \le \sqrt {2m}$的点, 最多有$\sqrt {2m}$条边, 满足条件; 对于$deg > sqrt {2m}$的点, 只会向$deg > \sqrt {2m}$的点连边, 最多也只有$\sqrt {2m}$条.